/*
  外星密码
  题目描述
    Pell 数列 {a1, a2, a3, ... } 的定义是这样的:
      a1 = 1,
      a2 = 2,
      ... ,
      an = 2 * a(n-1) + a(n-2)
       (说明: n > 2，
              a(n-1)表示数列中的第 n - 1 项，
              a(n-2)表示数列中的第 n - 2 项)
    Gordon 给出一个正整数 k, 要求 Pell 数列的第 k 项模上 32767 的值是多少。
  输入
    第 1 行是测试数据的组数 n (1 <= n <= 20),
    后面跟着 n 行输入。每组测试数据占 1 行，包括 1 个正整数 k (1 <= k <= 10^6)。
  输出
    n 行，每行输出对应一个输入。输出应是一个非负整数。
  样例输入
    2
    1
    8
  样例输出
    1
    408
*/